/**
 * 对称二叉树
 *
 * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
 *
 * 示例 1：
 * 输入：root = [1,2,2,3,4,4,3]
 * 输出：true
 *
 * 示例 2：
 * 输入：root = [1,2,2,null,3,null,3]
 * 输出：false
 *
 * 提示：
 * 树中节点数目在范围 [1, 1000] 内
 * -100 <= Node.val <= 100
 *
 * 进阶：你可以运用递归和迭代两种方法解决这个问题吗？
 */

/**
 * 和相同的是一样的思路, 只不过这里要传两个参数
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */

public class Main {

    public boolean isSymmetric(TreeNode root) {
        return dfs(root, root);
    }

    public boolean dfs (TreeNode x, TreeNode y) {

        if (x == null && y == null) {
            return true;
        }

        if (x == null && y != null
                || x != null && y == null) {
            return false;
        }

        if (x.val != y.val) {
            return false;
        }

        // 注意要传两边的节点, 因为值要判断对称
        return dfs(x.left, y.right) && dfs(x.right, y.left);
    }

}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}